class Solution {
public:
    vector<string> fullJustify(vector<string>& w, int maxWidth) {
        int n = w.size();
        int i = 0;
        vector<string> ret;
        while(i < n)
        {
            // 1. 取单词，直到单词所有字符加起来 <= maxWidth
            int len = 0;    // 每行长度
            int j;          // 让 j 往后走
            vector<string> temp;
            for(j = i; j < n && len + w[j].size() + (i == j ? 0 : 1) <= maxWidth; j++)
            {
                // (i == j ? 0 : 1) 从第二个单词开始，前面都要加一个空格
                len += w[j].size() + (i == j ? 0 : 1);

                // 暂存至temp中，表示这一行的文本
                temp.push_back(w[j]);
            }

            // 2. 加空格，每个单词后面都需要至少一个空格，除了最后一个单词
            int tempLen = temp.size();
            for(int k = 0; k < tempLen - 1; k++)
                temp[k] += " ";
            
            // 3. 处理每行应该再加入多少空格
            int blank = maxWidth - len;     // 可以继续添加的空格数量
            if(j == n)
            {
                // 如果是最后一行，仅需要在最后面加入空格
                while(blank--)
                    temp[temp.size() - 1] += " ";
            }
            else
            {
                // 不是最后一行，分两种情况
                // 这一行只有一个单词 or 有两个单词，那么也只需要在第一个单词末尾添加空格直至达到maxWidth
                // 只有一个单词的话，第一个也就是最后一个
                // "justification.    " or "This            is"
                if(temp.size() == 1 || temp.size() == 2)
                {
                    while(blank--)
                        temp[0] += " ";
                }
                else
                {
                    // 这一行有多个单词
                    // 则从左往右插入空格，就可以满足不能均匀分配时，左侧放置的空格数多于右侧的空格数的要求
                    for(int k = 0; blank > 0; blank--)    // 注意这里还是temp.size() - 1，因为最后一个单词依然不用在末尾添加空格
                    {
                        temp[k] += " ";
                        k = (k + 1) % (temp.size() - 1);
                    }
                }
            }
            // 从temp取出一行拼在一起
            string str;
            for(auto &s : temp)
                str += s;
            ret.push_back(str);

            i = j;  // 继续循环
        }
        return ret;
    }
};